package algorithm;

/**
 * 删除有序数组中的重复项II
 * 给出的数组是已经升序的了
 * 要求：使用O(1)的空间复杂度
 */
public class LeetCode_removeDuplicates_80 {

    public static void main(String[] args) {
        int[] nums = new int[]{1,3,4,5,};
        nums[0] = nums[1];
        System.out.println(nums[1]);
    }
    /**
     * 可行，但是执行的时间和空间还能优化
     * 初步的思路：使用双指针
     * @param nums
     * @return
     */
    public static int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len < 3) {
            return len;
        }

        for (int i = 0; i < len - 1; ) {
            int currCount = 1;
            int j = i + 1;
            for ( ; j < len; j++) {
                if (nums[j] == nums[j - 1]) {
                    currCount++;
                } else {
                    break;
                }
            }
            if (currCount > 2) {
                move(j - currCount + 2, j, len, nums);
                len = len - currCount + 2;
            }
            if (currCount == 2) {
                i += 2;
            } else {
                i += 1;
            }
            currCount = 1;
        }
        return len;
    }

    public static void move(int ahead, int startIndex, int len, int[] nums) {
        for (int i = ahead, j = startIndex; j < len; i++, j++) {
            nums[i] = nums[j];
        }
    }

    /**
     * 答案
     */
    public static int removeDuplicates(int[] nums, boolean noUsed) {
        int len = nums.length;
        if (len < 3) {
            return len;
        }
        int low = 2, fast = 2;
        while (fast < len) {
            if (nums[low - 2] != nums[fast]) {
                nums[low] = nums[fast];
                low++;
            }
            fast++;
        }
        return low;
    }

}
